// https://leetcode.cn/problems/number-of-islands/
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

class Solution {
public:
	vector <vector<int>> vi;
	int row = 0;
	int col = 0;
    int numIslands(vector<vector<char>>& grid) {
		row = grid.size();
        col = grid[0].size();
        int num = 0;
        
		vi.resize(row, vector<int>(col));
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (vi[i][j] == 1) continue;
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    num++;
                }
            }
        }
        return num;
    }
	
	void dfs(vector<vector<char>>& grid, int i, int j){
		if(i < 0 || j < 0 || i >= row || j >= col || vi[i][j] == 1 || grid[i][j] == '0') return;
		vi[i][j] = 1;
		dfs(grid, i + 1,j);
		dfs(grid, i - 1,j);
		dfs(grid, i ,j + 1);
		dfs(grid, i ,j - 1);
	}
};

int main(){
	Solution so;
	vector<vector<char>> nums = {
	  {'1','1','1','1','0'},
	  {'1','1','0','1','0'},
	  {'1','1','0','0','0'},
	  {'0','0','0','0','0'}
	};
	cout << so.numIslands(nums);
	return 0;
}